package com.cty.B_SpecialDataStructures.C_PriorityQ.PriorityQArray;

import com.cty.F_common.DataItem;

/**
 * @Auther: cty
 * @Date: 2020/6/14 17:03
 * @Description: 有序数组实现优先级队列
 * 应用场景：
 *      数据量可预测或内存充足时使用 数组实现优先级队列 或 数组堆实现优先级队列
 *          对插入要求不高时，考虑使用数组实现优先级队列
 *
 * 重要操作：
 *      ① insert(DataItem): boolean    O(N)
 *      ② remove(): DataItem    O(1)
 * @version: 1.0
 */
public class PriorityQArray {
    private int maxSize;
    private DataItem[] array;
    private int nItems;

    public PriorityQArray(int maxSize){
        this.maxSize = maxSize;
        array = new DataItem[maxSize];
        nItems = 0;
    }

    public boolean isEmpty(){
        return (nItems == 0);
    }

    public boolean isFull(){
        return (nItems == maxSize);
    }

    public int size(){
        return nItems;
    }

    public void displayPriorityQ(){
        for(int i=0; i<nItems; i++)
            System.out.print(array[i].getKey() + " ");
        System.out.println();
    }

    /**
     * 升序插入  O(N)
     * @param item
     * @return
     */
    public boolean insert(DataItem item){
        if(isFull())
            return false;

        int i;
        for(i=nItems-1; i>=0; i--)
            if(item.getKey() < array[i].getKey())
                array[i+1] = array[i];
            else
                break;

        array[i+1] = item;
        nItems++;
        return true;
    }

    /**
     * 移除最大  O(1)
     * @return
     */
    public DataItem remove(){
        if(isEmpty())
            return null;

        return array[--nItems];
    }

}  // end PriorityQArray{}
